package org.example.myleet.rosalind.full;

import org.example.myleet.rosalind.utils.AminoAcidMassReader;

import java.io.*;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class Solution {

    private static final BigDecimal UPSILON = BigDecimal.valueOf(0.0001);

    private static final BigDecimal MIN_MASS = BigDecimal.valueOf(57);
    private static final BigDecimal MAX_MASS = BigDecimal.valueOf(187);

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line;
        //parent mass
        BigDecimal parentMass = new BigDecimal((line = br.readLine()).trim());
        //ion mass list
        List<BigDecimal> ionMasses = new ArrayList<>();
        while (null != (line = br.readLine())) {
            line = line.trim();
            if (line.length() < 1) {
                break;
            }
            ionMasses.add(new BigDecimal(line));
        }
        ionMasses.sort(Comparator.naturalOrder());
        //n
        int n = ionMasses.size() / 2 - 1;
        //amino acid mass
        Map<String, BigDecimal> aminoAcidMapMass = AminoAcidMassReader.getAminoAcidMassMap();
        Map<String, String> massMapAminoAcid = new HashMap<>(aminoAcidMapMass.size());
        for (Map.Entry<String, BigDecimal> entry : aminoAcidMapMass.entrySet()) {
            massMapAminoAcid.put(entry.getValue().toPlainString(), entry.getKey());
        }
        boolean[] visited = new boolean[ionMasses.size()];
        StringBuilder peptide = new StringBuilder();
        for (int i = 0; i < ionMasses.size(); ++i) {
            BigDecimal mass = ionMasses.get(i);
            int j = 0;
            for (; j < ionMasses.size(); ++j) {
                BigDecimal suffix = parentMass.subtract(mass);
                if (suffix.subtract(ionMasses.get(j)).compareTo(UPSILON) < 0) {
                    break;
                }
            }
            visited[i] = true;
            visited[j] = true;
            backtrack(n, parentMass, ionMasses, massMapAminoAcid, visited, mass, peptide);
            visited[i] = false;
            visited[j] = false;
        }
        br.close();
    }

    private static void backtrack(int n, BigDecimal parentMass, List<BigDecimal> ionMasses, Map<String, String> massMapAminoAcid, boolean[] visited, BigDecimal prevMass, StringBuilder peptide) {
        if (peptide.length() >= n) {
            System.out.println(peptide);
            return;
        }
        for (int i = 0; i < ionMasses.size(); ++i) {
            if (visited[i]) {
                continue;
            }
            BigDecimal mass = ionMasses.get(i);
            BigDecimal diff = mass.subtract(prevMass);
            //如果diff小于最小的氨基酸mass，则往大的找
            if (diff.compareTo(MIN_MASS) <= 0) {
                continue;
            }
            //如果diff大于最大的氨基酸mass，则不用继续往下找，因为diff只会更大
            if (diff.compareTo(MAX_MASS) >= 0) {
                break;
            }
            String m = diff.setScale(5, RoundingMode.HALF_UP).toPlainString();
            String a = massMapAminoAcid.get(m);
            if (null != a) {
                //b-ion和y-ion产生的diff适配出一个氨基酸，则可能找到一个，连接到结果后面
                peptide.append(a);
                //下面标记已经访问过
                visited[i] = true;
                //找到和b-ion互补的y-ion的j，这个也要标记已被使用
                int j = 0;
                for (; j < ionMasses.size(); ++j) {
                    BigDecimal suffix = parentMass.subtract(mass);
                    if (suffix.subtract(ionMasses.get(j)).compareTo(UPSILON) < 0) {
                        break;
                    }
                }
                visited[j] = true;
                //DFS
                backtrack(n, parentMass, ionMasses, massMapAminoAcid, visited, mass, peptide);
                //回溯
                visited[j] = false;
                visited[i] = false;
                peptide.deleteCharAt(peptide.length() - 1);
            }
        }
    }
}
